package arrayandstring;
/**
 * https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others/
 */
public class E747_LargestNumberAtLeastTwiceofOthers {
    /**
     * 时间复杂度 O(n) 空间复杂度 O(1)
     * 第一次循环找到最大值
     * 第二次循环验证最大值是否符合要求
     */
    public int dominantIndex(int[] nums) {
        if (nums.length == 1) return 0;
        int max = nums[0], index = 0;
        for (int i = 1; i < nums.length; i++) {
            if (max < nums[i]) {
                max = nums[i];
                index = i;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (2*nums[i] > max && i != index) {
                return -1;
            }
        }
        return index;
    }
    /**
     * 官方解法
     * 时间复杂度 O(n) 空间复杂度 O(1)
     * 不需要与每个值作比较
     * 最大值大于2倍的第二大的值便符合要求
     */
    public int dominantIndex1(int[] nums) {
        if (nums.length == 1) return 0;
        int max = -1, second = -1, index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                second = max;
                max = nums[i];
                index = i;
            } else if (nums[i] > second) {
                second = nums[i];
            }
        }
        return max >= 2*second ? index : -1;
    }
}
